package com.jeff.learn.sort;

/**
 * 快速排序算法
 * 算法规则:
 * 1. 选择一个基准元素,通常选择第一个元素或者最后一个元素
 * 2. 遍历数组,将比基准元素小的元素放到左边,大的元素放到右边
 * 3. 递归左右两边的数组
 * 4. 直到数组长度为1,即排序完成
 * 优点:
 * 1. 快速排序是一种分治法的算法,它的时间复杂度为O(nlogn),比其他的排序算法(如冒泡排序)的平均时间复杂度要好
 * 2. 快速排序是一种不稳定的排序算法,它不保证元素的原有顺序
 * 3. 快速排序是一种原地排序算法,它只需要一个额外的栈空间,不需要额外的内存空间
 * 缺点:
 * 1. 快速排序的最坏情况时间复杂度为O(n^2),即数组已经排好序,但是仍然需要排序,这种情况称为退化
 * 2. 快速排序的空间复杂度为O(logn),即栈空间的开销
 * 3. 快速排序的不稳定性,使得它不适合于那些依赖于输入元素的顺序的应用,如排序链表
 * 4. 快速排序的原地排序,使得它不适合于那些需要额外空间的应用,如排序数组的部分元素
 * 应用:
 * 1. 排序数组
 * 2. 排序链表
 * 3. 搜索排序
 * 4. 数据库排序
 * 5. 多线程排序
 * 6. 图形图像排序
 * 7. 数值计算
 * 8. 机器学习排序
 * 9. 排序字符串
 * 10. 排序文件
 * 时间复杂度:O(nlogn)
 *
 * @author yaojianfeng
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3, 7};
        quickSort(arr, 0, arr.length - 1);
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    /**
     * 递归版快速排序算法
     *
     * @param arr   待排序数组
     * @param left  左边界
     * @param right 右边界
     */
    private static void quickSort(int[] arr, int left, int right) {
        // 递归终止条件
        if (left >= right) {
            return;
        }
        // 选择基准元素
        int pivot = partition(arr, left, right);
        // 递归左边数组
        quickSort(arr, left, pivot - 1);
        // 递归右边数组
        quickSort(arr, pivot + 1, right);
    }

    /**
     * 选择基准元素,并将数组分为左右两部分
     * 采用单边循环的方法,将数组分为左右两部分,左边部分的元素都小于基准元素,右边部分的元素都大于基准元素
     * @param arr   待排序数组
     * @param left  左边界
     * @param right 右边界
     * @return 基准元素的索引
     */
    private static int partition(int[] arr, int left, int right) {
        // 选择最后一个元素作为基准元素
        int pivot = arr[right];
        // 声明 大指针,用于记录大于基准元素的索引位置 从左边开始
        int bigPoint = left;
        // 声明 littlerIndex,用于记录小于基准元素的索引位置 从左边开始,到right-1结束
        int smallPoint = left;
        // 遍历数组 将大于基准元素的元素放到右边,小于基准元素的元素放到左边
        while (smallPoint < right) {
            // 如果当前元素小于基准元素,则将当前元素和大于基准元素的元素交换
            if (arr[smallPoint] < pivot) {
                // 当两个指针不一致时,才交换元素
                if (bigPoint != smallPoint) {
                    // 交换大于基准元素的元素和小于基准元素的元素
                    swap(arr, bigPoint, smallPoint);
                }
                // 大指针只有在 遇到大于基准元素的时候,指针后移
                bigPoint++;
            }
            // 小指针每次遍历都后移
            smallPoint++;
        }
        // 最后将基准元素与最后一个大于基准元素的元素交换
        swap(arr, bigPoint, right);
        // 返回基准元素的索引
        return bigPoint;
    }

    /**
     * 交换数组元素
     *
     * @param arr 待交换数组
     * @param i   索引i
     * @param j   索引j
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
